package two.chapter_1.c1_4;

import edu.princeton.cs.algs4.StdOut;
import two.chapter_1.c1_2.StaticSETofInts;

import java.util.Arrays;

public class Ex1_4_12 {


    public static void main(String [] args){

        int a[]={1,2,3,4,5,6,19,8,9,15};
        int b[]={10,12,13,14,15,6,7,18,9,9};
        Arrays.sort(a);
        Arrays.sort(b);
        intersection(a,b);
    }

    /**
     * 由于两个数组都是有序的，可以同时进行比较。
     *
     * 设 i, j 分别为两个数组的下标。
     * 如果 a[i] == a[j]，i 和 j 都向后移动一位。
     * 如果 a[i] != a[j]，比较小的那个向后移动一位。
     * 循环直到某个数组遍历完毕。
     *
     * 这样最后的时间复杂度 ~2N
     * @param a
     * @param b
     */
    private static void intersection(int a[],int b[]){
        int aN=a.length;
        int bN=b.length;
        for (int i=0,j=0;i<aN && j<bN;){
            if (a[i]<b[j]){
                i++;
            }else if (a[i]>b[j]){
                j++;
            }else {
                StdOut.println(a[i]);
                i++;
                j++;
            }


        }
    }
}
